package com.zs.letcode.binary_search;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 找出第 k 小的距离对
 * 给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
 * <p>
 * 示例 1:
 * <p>
 * 输入：
 * nums = [1,3,1]
 * k = 1
 * 输出：0
 * 解释：
 * 所有数对如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
 * 提示:
 * <p>
 * 2 <= len(nums) <= 10000.
 * 0 <= nums[i] < 1000000.
 * 1 <= k <= len(nums) * (len(nums) - 1) / 2.
 * 相关标签
 * 数组
 * 双指针
 * 二分查找
 * 排序
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xekymd/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/4 07:35
 */
public class Chapter21 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：堆 [超出时间限制]
         */
        private class Node {
            int root;
            int nei;

            public Node(int root, int nei) {
                this.root = root;
                this.nei = nei;
            }
        }

        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            PriorityQueue<Node> heap = new PriorityQueue<>(nums.length, Comparator.comparingInt(node -> nums[node.nei] - nums[node.root]));
            for (int i = 0; i + 1 < nums.length; i++) {
                heap.offer(new Node(i, i + 1));
            }
            Node node = null;
            for (; k > 0; --k) {
                node = heap.poll();
                if (node.nei + 1 < nums.length) {
                    heap.offer(new Node(node.root, node.nei + 1));
                }
            }
            return nums[node.nei] - nums[node.root];
        }

        /**
         * 方法二：二分查找 + 前缀和
         */
        public int smallestDistancePair1(int[] nums, int k) {
            Arrays.sort(nums);
            int WIDTH = 2 * nums[nums.length - 1];

            //multiplicity[i] = number of nums[j] == nums[i] (j < i)
            int[] multiplicity = new int[nums.length];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i - 1]) {
                    multiplicity[i] = 1 + multiplicity[i - 1];
                }
            }
            //prefix[v] = number of values <= v
            int[] prefix = new int[WIDTH];
            int left = 0;
            for (int i = 0; i < WIDTH; i++) {
                while (left < nums.length && nums[left] == i) left++;
                prefix[i] = left;
            }

            int lo = 0;
            int hi = nums[nums.length - 1] - nums[0];
            while (lo < hi) {
                int mi = (lo + hi) / 2;
                int count = 0;
                for (int i = 0; i < nums.length; i++) {
                    count += prefix[nums[i] + mi] - prefix[nums[i]] + multiplicity[i];
                }
                if (count >= k) hi = mi;
                else lo = mi + 1;
            }
            return lo;
        }

        /**
         * 方法三：二分查找 + 双指针 [通过]
         */
        public int smallestDistancePair2(int[] nums, int k) {
            Arrays.sort(nums);
            int lo = 0;
            int hi = nums[nums.length - 1] - nums[0];
            while (lo < hi) {
                int mi = (lo + hi) / 2;
                int count = 0, left = 0;
                for (int right = 0; right < nums.length; right++) {
                    while (nums[right] - nums[left] > mi) left++;
                    count += right - left;
                }
                if (count >= k) hi = mi;
                else lo = mi + 1;
            }
            return lo;
        }
    }
}
